package cn.good.yan.sf.t5;

/**
 * 5 合并链表  --  1 2 3 5 、 4 6 7  ----  1 2 3 4 5 6 7
 * 合并链表 - （小顶堆）
 *
 * @author shengren.yan
 * @create 2024-07-06
 */
public class MergeNode {


    private int value;
    public MergeNode next;

    public MergeNode(int value, MergeNode next) {
        this.value = value;
        this.next = next;
    }

    // 合并链表 方式1 ：
    public MergeNode merge1(MergeNode a, MergeNode b) {
        MergeNode head = new MergeNode(-1, null);
        MergeNode p = head;
        while (a != null && b != null) {
            if (a.value < b.value) {
                p.next = a;
                a = a.next;
            } else {
                p.next = b;
                b = b.next;
            }
            p = p.next;
        }
        if (a != null) {
            p.next = a;
        }
        if (b != null) {
            p.next = b;
        }
        return head.next;
    }

    // 合并链表 方式2 ：递归
    public MergeNode merge2(MergeNode a, MergeNode b) {
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }
        if (a.value < b.value) {
            a.next = merge2(a.next, b);
            return a;
        } else {
            b.next = merge2(a, b.next);
            return b;
        }
    }

    // 合并多个链表
    public MergeNode mergeAll(MergeNode[] arr) {
        if (arr.length == 0) {
            return null;
        }
        return cut(arr, 0, arr.length - 1);
    }

    private MergeNode cut(MergeNode[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        int m = (i + j) >>> 1;
        MergeNode left = cut(arr, i, m);
        MergeNode right = cut(arr, m + 1, j);
        return merge1(left, right);
    }

    public static void main(String[] args) {
        MergeNode a3 = new MergeNode(5, null);
        MergeNode a2 = new MergeNode(3, a3);
        MergeNode a1 = new MergeNode(1, a2);

        MergeNode b5 = new MergeNode(8, null);
        MergeNode b4 = new MergeNode(7, b5);
        MergeNode b3 = new MergeNode(4, b4);
        MergeNode b2 = new MergeNode(2, b3);
        MergeNode b1 = new MergeNode(2, b2);

        System.out.println("------------");
        // 方式1：
//        MergeNode r1 = a1.merge1(a1, b1);
//        r1.loop();
        // 方式2：
//        MergeNode r2 = a1.merge2(a1, b1);
//        r2.loop();
        // 方式3：
        MergeNode c3 = new MergeNode(10, null);
        MergeNode c2 = new MergeNode(9, c3);
        MergeNode c1 = new MergeNode(1, c2);
        MergeNode d2 = new MergeNode(14, null);
        MergeNode d1 = new MergeNode(12, d2);
        MergeNode[] arr = {
                a1, b1, c1, d1
        };
        MergeNode r3 = a1.mergeAll(arr);
        r3.loop();

    }

    public void loop() {
        for (MergeNode i = this; i != null; i = i.next) {
            System.out.println(i.value);
        }
    }


}
